﻿using System;
using System.Linq;

class SubsetSum
{
    static void Main()
    {
        Console.Write("Number of elements of array:");
        int arrayLength = int.Parse(Console.ReadLine());
        int[] inputArray = new int[arrayLength];
        for (int i = 0; i < arrayLength; i++)
        {
            Console.Write("\nElement a[{0}]:", i);
            inputArray[i] = (int.Parse(Console.ReadLine()));
        }
        Console.Write("Targeted sum:");
        int expectedSum = int.Parse(Console.ReadLine());


        //int[] inputArray = { 2, 1, 2, 4, 3, 5, 2, 6 };
        //int expectedSum = 25;


        int[] array = new int[inputArray.Length];

        Subset(inputArray.Length - 1, array, inputArray, expectedSum);
    }

    static void Subset(int n, int[] subsetsArray, int[] inputArray, int expectedSum)
    {
        if (n < 0)
        {
            if (subsetsArray.Sum() == expectedSum)
            {
                Print(subsetsArray); 
            }
            return;
        }

        for (int i = 0; i < 2; i++)
        {
            subsetsArray[n] = i * inputArray[n];
            Subset(n - 1, subsetsArray, inputArray, expectedSum);
        }
    }

    static void Print(int[] array)
    {
        for (int i = 0; i < array.Length; i++)
        {
            if (array[i] != 0)
            {
                Console.Write(" " + array[i]);               
            }
        }
        Console.WriteLine();
    }
}